package leetcode21_30;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author shhjiang_001
 * @create 2020-06-13 20:40
 */
public class Solution22 {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList();
        if(n <= 0){
            return null;
        }
        method1(new char[2*n],0,list);
        return list;
    }
    public void method1(char[] current,int pos ,List<String> result){
        if(pos == current.length){
            if(valid(current)) result.add(new String(current));
        }else{
            current[pos] = '(';
            method1(current,pos+1,result);
            current[pos] = ')';
            method1(current,pos+1,result);


        }
    }
    public boolean valid(char[] current){
        int balance = 0;
        for(char c:current){
            if(c == '(') balance++;
            else balance--;
            if(balance < 0) return false;
        }
        return balance==0;
    }

    @Test
    public void test(){
        Solution22 solution22 = new Solution22();
        List<String> strings = solution22.generateParenthesis(3);
        for (int i = 0;i < strings.size();i++){
            System.out.println(strings.get(i));
        }
    }
}
